package com.algorithm.leetCode.topic;

import java.util.Arrays;
import java.util.HashMap;

/**
 * <p>
 *
 * </p>
 *
 * @author lzt
 * @version 1.0
 * @since 2024/1/22 14:39
 */
public class Dichotomy {

    /**
     * 给你一个非负整数 x ，计算并返回 x 的 算术平方根 。
     * 由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。
     */
    public static int mySqrt(int x) {

        if (x == 0) {
            return 0;
        }
        long a = 0;
        long b = 0;
        long i = 0;
        for (i = 0; i < x; i++) {
            a = i * i;
            b = (i + 1) * (i + 1);
            if ((x > a && x < b) || x == a) {
                return (int) i;
            }
            if (x == b) {
                return (int) (i + 1);
            }

        }
        return -1;

    }
    public static int mySqrt1(int x) {
        if (x == 0) {
            return 0;
        }

        int left = 1;
        int right = x;

        while (left <= right) {
            int mid = left + (right - left) / 2;
            int mid_sq = x / mid;

            if (mid_sq == mid) {
                return mid;
            } else if (mid_sq > mid) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return right;
    }

    /**
     * 给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数
     */
    public static int missingNumber(int[] nums) {
        int[] aa = new int[nums.length + 1];
        Arrays.fill(aa, -1);
        for (int num : nums) {
            aa[num] = num;
        }
        int i = 0;
        for (; i < aa.length; i++) {
            if (i != aa[i]) {
                return i;
            }
        }
        return i;
    }

    /**
     * 给定两个数组 nums1 和 nums2 ，返回 它们的交集 。
     * 输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序
     */
    public static int[] intersection(int[] nums1, int[] nums2) {
        HashMap<Integer,Integer> a = new HashMap<>();
        int z = 0;
        for(int n :nums1) {
            for(int i :nums2) {
                if(i == n && (i != z || i == 0)) {
                    a.put(i,i);
                    z = i;
                }
            }
        }
        int[] sum = new int[a.size()];
        int i = 0;
        for (Integer value : a.values()) {
            sum[i] = value;
            i++;
        }
        return sum;
    }


}
